The invention pertains to methods and apparatus which enable a computer user to verify whether they have correctly input their password into a computer. More specifically, the invention pertains to methods and apparatus which ensure that a password which a user inputs into a computer is the password which the user intended to input into the computer, and not a permutation thereof.
When encrypting a file, a computer user is often asked to input a password. The password is used to generate an encryption key, and the key is then used to encrypt a file or files. To decrypt the file or files, the user, or someone to whom the user has disclosed their password, must re-input the user""s password exactly as it was input during the file encryption process.
To increase the likelihood that an attacker will not be able to guess and/or reverse engineer a password, various constraints and latitudes can be associated with a password. An example of a constraint is that a password has to comprise at least eight characters. An example of a latitude is that a password can comprise not only any letter in the alphabet (upper or lower case), but also any number or special character which a user may input into a computer via the computer""s attached keyboard.
A problem with user input passwords is that they are sometimes mistyped. When a user mistypes their password during file decryption, the penalty is not being able to open an encrypted file or files, and the fix is to retype the password correctly. The penalty is small, and the fix is simple. When a user mistypes their password during file encryption, the penalty is once again an inability to open the encrypted file or files. However, the fix is much more difficult since the number of ways in which a password can be mistyped is voluminous, and once a file has been encrypted with a mistyped password, one""s knowledge of the intended password does not yield a simple fix, as it is the apropriately mistyped password which one needs to know.
In the simplest cases of mistyping, a user mistypes one or more letters of their password. For example, HOUSE might become HLUSE or HLESE. However, in more severe cases of mistyping, a user might misplace their hands on a keyboard. Thus, HOUSE might become JPIDR. Although this second form of mistyping occurs with less frequency, it does happen and its effects can be catastrophic. If a user has no knowledge of their mistyped password, and no knowledge of a computer""s means for generating an encryption key (which will most always be the case), then a file or files encrypted with a mistyped password can be forever lost.
The problem of encrypting a file with a mistyped password is compounded by the fact that many password entry prompts do not display a password as it is typed. Instead, a number of asterisks or other meaningless characters are displayed. While such placeholder characters prevent an onlooker from seeing a user""s password, they further the likelihood that a user will encrypt a file with a mistyped password.
The most common solution to the problem of mistyped passwords is to force a user to type their password twice in succession. The successively typed passwords are then compared to ensure that they are identical. If there is any difference between the two passwords, the user is prompted to repeat the entire password entry procedure. While this solution discovers some mistyped passwords, it does have its disadvantages. For one, the necessity of having to type a password twice discourages some users from selecting the longer passwords which are typically necessary for strong encryption. Furthermore, repetitive typing of a password does not guarantee that all mistypings of a password will be discovered. For example, repetitive password typing will not detect problems such as having the caps lock on unintentionally, or having one""s fingers shifted with respect to a keyboard.
Another solution to the problem of mistyped passwords is to have software generate a number of check characters that must be typed with a password. The check characters are a function of the rest of the characters in the password and may be generated, for example, by submitting the password as a whole to a hash function. Software can then verify whether the password and the check characters correspond. If they do, the password is accepted. If they do not, the password is rejected. While this solution provides greater protection against mistyped passwords than does the repetitive typing solution, it also tends to weaken encryption. Since a user is forced to remember their base password, as well as a seemingly random number of check characters, many users will shorten their base password so as to keep the total number of characters which need to be remembered to a manageable number (maybe 8-10). Thus, instead of typing in an 8-10 character password, a user might type in a less secure password of maybe 5-7 characters so that once the computer generates 3 or so check characters, the user need only remember a total of 8-10 characters. Unfortunately, the 8-10 characters which include check characters are not as strong from an encryption standpoint as 8-10 characters which are all independent from one another. The use of check characters to prevent mistyped passwords can therefore result in weaker encryption for some users. On the other hand, users who are more concerned about the strength of their password might continue to use longer base passwords, possibly taking advantage of the full number of characters allotted for a password (e.g., 20). However, if software receives a 20 character password, and then generates additional check characters, most users will be forced to write down their password. At a minimum, most users will be forced to write down the check characters. Although a 23 character password having a 20 character base password will provide as strong or stronger encryption than a 20 character base password standing alone, the fact that some or all of the 23 character password will need to be written down increases the likelihood that an attacker might discover the paper (or file) on which the password is recorded. Since most users rely on commercially available encryption/decryption software, once an attacker discovers a user""s password or check characters, it is often a fairly easy task to reverse engineer the missing element(s) of the user""s password. At a minimum, discovery of the check characters can reduce the number of trials which an attacker needs to make to xe2x80x9ccrackxe2x80x9d an encrypted message.
A need therefore exists for a better method of insuring that a password input into a computer is the password which a user intended to input into the computer.
In achievement of the foregoing need, the inventor has devised a new form of password verification system.
The system receives a user""s password input and subjects the input to a hash function. The hash function produces an N-bit number of, for example, fourteen bits. The N-bit number is then divided into two smaller numbers (e.g., two 7-bit numbers), and the two smaller numbers are used as indexes into a word list (e.g., a 128 word list). The two words which are indexed by the two 7-bit numbers are retrieved and presented to the user along with a verification prompt. The verification prompt simply asks the user to indicate 1) whether the two words are recognizable as being those which correspond to the user""s password, 2) whether it is known to the user that the two words do not correspond to the user""s password, or 3) whether the user is unsure if the two words correspond to their password.
If the user has input a password for the first time, they will have no way of knowing whether the two words which are presented are the two words which correspond to their password. In this case, the user will need to indicate their uncertainty, and the system will prompt the user to re-input their password. If the user""s re-input password is identical to their first input password, the system will accept the user""s password, and the user will know that the words which were presented to them are the ones which correspond to their password.
If a user knows that the presented words are the ones which correspond to their password (i.e., the words are the right ones), all the user needs to do is indicate to the system that they recognize the words and their password will be accepted. Preferably, such an indication can be made by simply typing a xe2x80x9cyxe2x80x9d for YES, clicking on a YES button, or speaking YES into an audio transducer. As a result, if a user correctly types their password and then recognizes the check words which are presented to them as being the right ones, the only penalty which the user incurs is a single keystroke (i.e., typing xe2x80x9cyxe2x80x9d for YES), a single mouse click, or a single voiced response.
If a user knows which check words are supposed to be presented, but doesn""t see (or hear) these words in the verification prompt which is presented, the user can indicate to the system that they don""t recognize the presented words, and the user will be prompted to re-input their password.
As will be explained in greater detail below, in a system which retrieves two words from a 128 word list, there is a one in 16,384 chance that two different passwords will map to the same two xe2x80x9ccheckxe2x80x9d words. As a result, a user can be fairly certain that if two check words are recognizable, they have input their password correctly. The user can also be fairly certain that if they are presented with two check words which aren""t recognizable, they have mis-input their password.
With such a system, there is no need to remember check characters (or check words) which must be input from memory. Rather, a user need only be able to recall after prompting that two check words are familiar. As a result, the user is free to input a long password which they find easy to remember, and there is no need to worry that their long password is going to be made even longer by a system which adds additional check characters to their password.
Furthermore, if a user recognizes two check words as being correct, they need only make a single additional keystroke or other response to verify that their password was correctly input. Thus, a user does not need to re-input their entire password to verify the correctness of their password, and in a keyboard-based system, the user saves several keystrokes over verification methods which require a user to retype their password.